/*
 * 1455. 合法数组
 * 如果一个数组中只包含一个出现了奇数次的数，那么数组合法，否则数组不合法。输入一个只包含正整数的数组 a，判断该数组是否合法，如果合法返回该出现了奇数次的数，如果不合法返回 -1。
 * https://www.lintcode.com/problem/valid-array/description
 * 
 * 样例
 * 给出 a=[1,1,2,2,3,4,4,5,5]，返回 3。
 * 解释：
 * 该数组只有 3 出现了奇数次，因此数组合法，返回 3。
 * 
 * 给出 a=[1,1,2,2,3,4,4,5]，返回 -1。
 * 解释：
 * 该数组中 3 和 5 都出现了奇数次，因此数组不合法，返回 -1。
 *  
 * 2018.06.23 @jeyming
 */
package valid_array_1455;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Valid_array_1455 {
	/**
	 * @param a: The array.
	 * @return: The number which has odd number of times or -1.
	 */
	public static int isValid(List<Integer> a) {
		// Write your code here
		Collections.sort(a);
		List<Integer> result = new ArrayList<Integer>();
		Integer tmp = a.get(0);
		int cnt = 1;
		for(int i = 1; i < a.size() + 1; ++i) {
			if((i < a.size()) && (tmp == a.get(i))) {
				++cnt;
			} else {
				if(cnt % 2 != 0) {
					result.add(tmp);
					if(result.size() > 1) {
						return -1;
					}
				}
				if(i < a.size()) {
					tmp = a.get(i);
					cnt = 1;
				}
			}
		}
		if(result.size() == 0)
			return -1;
		return result.get(0);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<Integer> list = new ArrayList<Integer>();
		list.add(1);
		list.add(1);
		list.add(2);
		list.add(2);
		list.add(3);
		list.add(4);
		list.add(4);
		list.add(4);
		list.add(4);
		System.out.println(isValid(list));

	}

}
